Линейный дискриминантный анализ

Предположения

Линейный дискриминантный анализ (Linear Discriminant Analysis, LDA) — это упрощённая модель квадратичного дискриминантного анализа при предположении, что все классы распределены нормально с общей ковариационной матрицей $\Sigma$:

$$p(\boldsymbol{x} | y) = \frac{1}{(2\pi)^{D/2} |\Sigma|^{1/2}} \exp \left( -\frac{1}{2} (\boldsymbol{x} - \boldsymbol{\mu}_y)^T \Sigma^{-1} (\boldsymbol{x} - \boldsymbol{\mu}_y) \right)$$

где $D$ — размерность пространства признаков.

Геометрический смысл предположения метода

Общность ковариационной матрицы означает, что распределение точек всех классов имеют идентичную форму и ориентацию, а различаются только положением своих центров $\boldsymbol{\mu}_y$.

Вывод дискриминантной функции

В генеративных моделях дискриминантные функции имеют следующий вид:

$$g_y(\boldsymbol{x}) = \ln p(\boldsymbol{x}|y) + \ln p(y),\quad y=1,2,...C$$

Найдём их аналитически, подставив выражение для $p(\boldsymbol{x}|y)$:

$$\begin{aligned} g_y(\boldsymbol{x}) &= \ln \left( \frac{1}{(2\pi)^{D/2} |\Sigma|^{1/2}} \right) - \frac{1}{2} (\boldsymbol{x} - \boldsymbol{\mu}_y)^T \Sigma^{-1} (\boldsymbol{x} - \boldsymbol{\mu}_y) + \ln p(y) \\ &= -\frac{D}{2}\ln(2\pi)-\frac{1}{2}\ln|\Sigma|-\frac{1}{2} (\boldsymbol{x} - \boldsymbol{\mu}_y)^T \Sigma^{-1} (\boldsymbol{x} - \boldsymbol{\mu}_y) + \ln p(y) \end{aligned}$$

Отбрасывая общее для всех $g_y(\boldsymbol{x})$ слагаемое $-\frac{D}{2}\ln(2\pi)-\frac{1}{2}\ln|\Sigma|$, получаем окончательный вид дискриминантных функций:

$$g_y(\boldsymbol{x})=-\frac{1}{2} (\boldsymbol{x} - \boldsymbol{\mu}_y)^T \Sigma^{-1} (\boldsymbol{x} - \boldsymbol{\mu}_y) + \ln p(y)$$

Геометрический смысл прогнозов

Из вида дискриминантной функции видно, что построение прогнозов методом LDA можно интерпретировать как переход в новое декоррелированное пространство признаков $\boldsymbol{x}' = \Sigma^{-1/2}\boldsymbol{x}$, где множество объектов становится сферическим, после чего объект в обновлённом пространстве относится к классу с ближайшим центроидом $\boldsymbol{\mu}_y$ с поправкой на частотность каждого класса.

Раскроем квадратичную форму:

$$\begin{aligned} g_y(\boldsymbol{x}) &= -\frac{1}{2} (\boldsymbol{x}^T \Sigma^{-1} \boldsymbol{x} - \boldsymbol{x}^T \Sigma^{-1} \boldsymbol{\mu}_y - \boldsymbol{\mu}_y^T \Sigma^{-1} \boldsymbol{x} + \boldsymbol{\mu}_y^T \Sigma^{-1} \boldsymbol{\mu}_y) + \ln p(y) \\ &= -\frac{1}{2} \boldsymbol{x}^T \Sigma^{-1} \boldsymbol{x} + \boldsymbol{x}^T \Sigma^{-1} \boldsymbol{\mu}_y - \frac{1}{2} \boldsymbol{\mu}_y^T \Sigma^{-1} \boldsymbol{\mu}_y + \ln p(y) \end{aligned}$$

Заметим, что слагаемое $-\frac{1}{2} \boldsymbol{x}^T \Sigma^{-1} \boldsymbol{x}$ одинаково для всех классов. Отбросив его, получим итоговую линейную дискриминантную функцию:

$$g_y(\boldsymbol{x}) = \boldsymbol{x}^T \Sigma^{-1} \boldsymbol{\mu}_y - \frac{1}{2} \boldsymbol{\mu}_y^T \Sigma^{-1} \boldsymbol{\mu}_y + \ln p(y)$$

Данная функция линейна по $\boldsymbol{x}$, поэтому метод LDA является линейным классификатором, разделяющим классы линейными гиперплоскостями.

Особенности метода

В отличие от QDA, где количество параметров растёт как $O(C \cdot D^2)$, в LDA мы оцениваем только одну ковариационную матрицу, общую для всех классов, поэтому число параметров растёт как $O(D^2)$.

Это делает метод более простым и менее склонным к переобучению, по сравнению с QDA. Общая ковариационная матрица менее склонна к вырождению, чем матрицы отдельных классов в QDA, особенно, когда есть классы, содержащие мало наблюдений.

Тем не менее, для большого числа признаков и малого числа наблюдений либо в случае линейной зависимости признаков даже общая ковариационная матрица может вырождаться или быть плохо обусловленной.

В таких случаях применяют регуляризацию, смешивая ковариационную матрицу с единичной матрицей:

$$\hat{\Sigma}_{reg} = (1 - \alpha) \hat{\Sigma} + \alpha \sigma^2 I$$

где $\alpha$ — гиперпараметр регуляризации, а $\sigma^2$ — средняя дисперсия всех признаков.